package com.lims.algorithm.algset.tree;

import java.util.Queue;
import java.util.concurrent.LinkedBlockingDeque;

/**
 * <描述:>红黑树（红黑树旋转时为保持红黑规则要先换色再旋转）
 *
 * @author lims
 * @date 2020-04-26 00:46
 */
public class RBTree<T extends Comparable<T>> {
    /**
     * 结点红色标记
     */
    private static final boolean RED = false;
    /**
     * 结点黑色标记
     */
    private static final boolean BLACK = true;

    /**
     * 红黑树结点类
     */
    static class RBNode<T extends Comparable<T>> {
        /**
         * 颜色
         */
        boolean color;
        T key;
        RBNode<T> left;
        RBNode<T> right;
        RBNode<T> parent;

        public RBNode(T key, boolean color, RBNode<T> parent, RBNode<T> left, RBNode<T> right) {
            this.key = key;
            this.color = color;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 根结点
     */
    private RBNode<T> rbtRoot;

    public RBTree() {
        rbtRoot = null;
    }

    private RBNode<T> parentOf(RBNode<T> node) {
        return node != null ? node.parent : null;
    }

    private boolean colorOf(RBNode<T> node) {
        return node != null ? node.color : BLACK;
    }

    private boolean isRed(RBNode<T> node) {
        return ((node != null) && (node.color == RED)) ? true : false;
    }

    private boolean isBlack(RBNode<T> node) {
        return !isRed(node);
    }

    private void setBlack(RBNode<T> node) {
        if (node != null) {
            node.color = BLACK;
        }
    }

    private void setRed(RBNode<T> node) {
        if (node != null) {
            node.color = RED;
        }
    }

    private void setParent(RBNode<T> node, RBNode<T> parent) {
        if (node != null) {
            node.parent = parent;
        }
    }

    private void setColor(RBNode<T> node, boolean color) {
        if (node != null) {
            node.color = color;
        }
    }

    /**
     * 先序遍历
     */
    public void preOrderRecur() {
        preOrderRecur(rbtRoot);
    }

    private void preOrderRecur(RBNode<T> avlNode) {
        if (avlNode == null) {
            return;
        }
        System.out.print(avlNode.key + " ");
        preOrderRecur(avlNode.left);
        preOrderRecur(avlNode.right);
    }

    /**
     * 中序遍历
     */
    public void inOrderRecur() {
        inOrderRecur(rbtRoot);
    }

    private void inOrderRecur(RBNode<T> avlNode) {
        if (avlNode == null) {
            return;
        }
        inOrderRecur(avlNode.left);
        System.out.print(avlNode.key + " ");
        inOrderRecur(avlNode.right);
    }

    /**
     * 后序遍历
     */
    public void postOrderRecur() {
        postOrderRecur(rbtRoot);
    }

    private void postOrderRecur(RBNode<T> avlNode) {
        if (avlNode == null) {
            return;
        }
        postOrderRecur(avlNode.left);
        postOrderRecur(avlNode.right);
        System.out.print(avlNode.key + " ");
    }

    /**
     * 层序遍历
     */
    public void levelOrder() {
        levelOrder(this.rbtRoot);
    }

    private void levelOrder(RBNode<T> RBNode) {
        if (RBNode == null) {
            return;
        }
        Queue<RBNode<T>> queue = new LinkedBlockingDeque<>();
        RBNode<T> cur;
        queue.add(RBNode);

        while (!queue.isEmpty()) {
            cur = queue.remove();
            System.out.print(cur.key + " ");
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }
    }

    /**
     * 左旋(x)
     * *
     * *       root                    root
     * *       /                       /
     * *      x                        y
     * *    /  \        -->>         /  \
     * *   lx   y                   x   ry
     * *      /  \                /  \
     * *     ly   ry             lx   ly
     * *
     */
    public void lRotate(RBNode<T> RBNode) {
        // 左旋后的新顶点（替代rbtNode）
        RBNode<T> lRotateNode = RBNode.right;
        // 新顶点的左子挂到新位置
        RBNode.right = lRotateNode.left;
        if (lRotateNode.left != null) {
            // 挂新位置后改变父结点指针
            lRotateNode.left.parent = RBNode;
        }

        // 新顶点开始代替旧顶点，旧顶点作为新顶点的左子
        lRotateNode.parent = RBNode.parent;
        if (RBNode.parent == null) {
            this.rbtRoot = lRotateNode;
        } else {
            // 新结点的父指针指向问题，作为父结点的左子还是右子
            if (RBNode.parent.left == RBNode) {
                // 作为左子
                RBNode.parent.left = lRotateNode;
            } else {
                // 作为右子
                RBNode.parent.right = lRotateNode;
            }

        }

        // 新结点替代
        lRotateNode.left = RBNode;
        RBNode.parent = lRotateNode;
    }

    /**
     * 右旋(x)
     * *       py                      py
     * *       /                       /
     * *      y                        x
     * *    /  \        -->>         /  \
     * *   x   ry                   lx   y
     * *  / \                          /  \
     * * lx rx                        rx  ry
     * *
     */
    public void rRotate(RBNode<T> RBNode) {
        RBNode<T> rRotateNode = RBNode.left;
        RBNode.left = rRotateNode.right;
        if (rRotateNode.right != null) {
            rRotateNode.right.parent = RBNode;
        }
        rRotateNode.parent = RBNode.parent;
        if (RBNode.parent == null) {
            this.rbtRoot = rRotateNode;
        } else {
            if (RBNode == RBNode.parent.left) {
                RBNode.parent.left = rRotateNode;
            } else {
                RBNode.parent.right = rRotateNode;
            }
        }

        rRotateNode.right = RBNode;
        RBNode.parent = rRotateNode;
    }

    /**
     * 插入
     */
    public void insert(T key) {
        RBNode insertNode = new RBNode(key, RED, null, null, null);
        if (insertNode != null) {
            insert(insertNode);
        }
    }

    private void insert(RBNode<T> insertNode) {
        int cmp;
        RBNode<T> parentNode = null;
        RBNode<T> current = this.rbtRoot;

        // 1.红黑树当做一个二叉查找树，结点添加到二叉查找树中
        while (current != null) {
            parentNode = current;
            cmp = insertNode.key.compareTo(current.key);
            if (cmp < 0) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        // 插入后设置父结点指针
        insertNode.parent = parentNode;
        if (parentNode != null) {
            cmp = insertNode.key.compareTo(parentNode.key);
            if (cmp < 0) {
                parentNode.left = insertNode;
            } else {
                parentNode.right = insertNode;
            }
        } else {
            this.rbtRoot = insertNode;
        }

        // 2.设置结点颜色
        insertNode.color = RED;

        // 3.修正红黑树，调整
        insertFixUp(insertNode);
    }

    /**
     * 插入修正函数
     * <p>
     * 父结点为红时，需要变色，考虑3种情况:
     * <p>
     * 1.p为红，u为红：
     * *    （p变黑，u变黑； -->> gp变红； -->> gp作当前结点继续）
     * *
     * 2.p为红，u为黑，p为gp的左子：
     * *    2.1 cur为p的左子（左顺链）：
     * *        （p变黑，gp变红 -->> gp右旋）
     * *    2.2 cur为p的右子
     * *        （p左旋; -->> 交换p和cur指针； -->> 同情况2.1，继续变色旋转）
     * *
     * 3.p为红，u为黑，p为gp的右子：
     * *    3.1 cur为p的右子（右顺链）：
     * *        （p变黑，gp变红 -->> gp左旋）
     * *    3.2 cur为p的左子：
     * *        （p右旋; -->> 交换p和cur指针； -->> 同情况3.1，继续变色旋转）
     * *
     */
    private void insertFixUp(RBNode<T> RBNode) {
        // 父结点
        RBNode<T> p;
        // 祖父
        RBNode<T> gp;

        while ((p = parentOf(RBNode)) != null &&
                (isRed(p))) {
            gp = parentOf(p);
            if (gp == null) {
                // 根结点变黑
                setBlack(this.rbtRoot);
                return;
            }
            if (p == gp.left) {
                // p为gp左子

                // 叔叔结点(uncle)
                RBNode<T> u = gp.right;
                // 1.p为红，u为红
                if (isRed(u)) {
                    // p变黑，u变黑； -->> gp变红； -->> gp作当前结点（继续）
                    setBlack(p);
                    setBlack(u);
                    setRed(gp);
                    RBNode = gp;
                    continue;
                }

                // 2.不为左顺链时
                if (RBNode == p.right) {
                    // p左旋; -->> 交换p和cur指针； -->> 同情况3（继续变色旋转即可）
                    lRotate(p);
                    RBNode<T> tmp;
                    tmp = p;
                    p = RBNode;
                    RBNode = tmp;
                }

                // 3.左顺链时
                // p变黑，gp变红 -->> gp右旋
                setBlack(p);
                setRed(gp);
                rRotate(gp);
            } else {
                // p为gp右子

                // 叔叔结点
                RBNode<T> u = gp.left;

                // 1.p为红，u为红
                if (isRed(u)) {
                    // p变黑，u变黑； -->> gp变红； -->> gp作当前结点（继续）
                    setBlack(p);
                    setBlack(u);
                    setRed(gp);
                    RBNode = gp;
                    continue;
                }

                // 2.不是右顺链
                if (RBNode == p.left) {
                    // p右旋; -->> 交换p和cur指针； -->> 同情况3（继续变色旋转即可）
                    rRotate(p);
                    RBNode<T> tmp;
                    tmp = p;
                    p = RBNode;
                    RBNode = tmp;
                }

                // 3.右顺链
                // p变黑，gp变红 -->> gp左旋
                setBlack(p);
                setRed(gp);
                lRotate(gp);
            }
        }
        // 根结点变黑
        setBlack(this.rbtRoot);
    }

    /**
     * 查找"二叉树x"中键值为key的节点（非递归）
     *
     * @param key
     * @return
     */
    public RBNode<T> search(T key) {
        return search(this.rbtRoot, key);
    }

    private RBNode<T> search(RBNode<T> RBNode, T key) {
        while (RBNode != null) {
            int cmpFlag = key.compareTo(RBNode.key);
            if (cmpFlag == 0) {
                return RBNode;
            }
            if (cmpFlag > 0) {
                RBNode = RBNode.right;
            } else if (cmpFlag < 0) {
                RBNode = RBNode.left;
            }
        }
        return null;
    }

    /**
     * 删除结点
     */
    public void remove(T key) {
        RBNode<T> delNode;
        if ((delNode = search(key)) != null) {
            remove(delNode);
        }
    }

    private void remove(RBNode<T> delNode) {
        // 替代结点（待删除结点有双子时，最后真实删除的结点） y
        RBNode<T> replace;
        // 替代结点的孩子（待删除结点有双子时，为后继结点的右孩子） x
        RBNode<T> childX;

        // replace的父结点
        RBNode<T> parentX;

        // 找到替代结点
        if (delNode.left == null || delNode.right == null) {
            replace = delNode;
        } else {
            // 有双子 用后继结点替代
            replace = delNode.right;
            while (replace.left != null) {
                replace = replace.left;
            }
        }

        // 找到替代结点的孩子
        if (replace.left != null) {
            childX = replace.left;
        } else {
            childX = replace.right;
        }

        // childX为null时，父结点指向null，null为黑结点
        if (childX != null) {
            // 开始删除真实的替代结点（child挂到replace位置）
            childX.parent = replace.parent;
        }
        if (replace.parent == null) {
            // 孩子结点作为根结点（这种情况只出现在 删除结点为根结点，且删除结点只有一个孩子）
            this.rbtRoot = childX;
        } else {
            if (replace == replace.parent.left) {
                // 子结点挂到replace位置
                replace.parent.left = childX;
            } else {
                replace.parent.right = childX;
            }
        }
        // 替代结点的父结点
        parentX = replace.parent;

        // 用replace的值替换掉删除结点的值（只有删除结点有双子的情况下，删除结点为叶子或者只有一个子结点时直接替换结点）
        // 删除结点为叶子或者只有一个子结点时，replace指向的就是rbtNode。
        if (replace != delNode) {
            // 删除结点有双子时，替换值
            delNode.key = replace.key;
        }

        // 如果真实删除结点为黑色，则需要调整
        if (isBlack(replace)) {
            removeFixUp(childX, parentX);
        }

        replace = null;
    }

    /**
     * 删除后调整平衡
     * 红黑树特性：一个结点有一个黑子，那一定有另一个黑子构成双子。红子可以作为一子。
     * x  ：为真实删除结点的孩子（后继结点的孩子）
     * b  ：兄弟结点
     * p  ：父结点
     * gp ：祖父
     * bl ：兄弟的左孩子
     * br ：兄弟的右孩子
     * <p>
     * 最后p，b，红色的br（bl）顺链时，变换结束
     * <p>
     * 调整情况（x增加一个额外的虚拟黑色，替代删除的黑色，保持红黑规则暂时性满足）：
     * 1.x为“红+黑”，直接变黑
     * 2.x为“黑+黑”，但x是根结点，直接变黑
     * 3.x为“黑+黑”，x不为根结点(4种情况)：
     * *
     * *    （1） b红                     -->> 转换为（2）、（3）、（4）
     * *    （2） b黑，bl黑，br黑。         -->> 黑色上浮，结束/转为（3）、（4）
     * *    （3） b黑，bl红，br黑。（不顺链） -->> 换色旋转，转为（4）
     * *    （4） b黑，br红，bl任意（顺链）   -->> 换色，旋转，为保持红黑规则可消除多余黑色
     * *
     * * x为左子、x为右子分类讨论，思路一致，left，right，旋转反过来即可
     * *
     *
     * @param RBNodeX 替代结点的孩子（x）
     * @param parentX  替代结点的父结点，也为x的父结点
     */
    private void removeFixUp(RBNode<T> RBNodeX, RBNode<T> parentX) {
        // x 的兄弟结点
        RBNode<T> brother;

        // 根结点和红色的直接变黑即可
        while (RBNodeX != rbtRoot && isBlack(RBNodeX)) {
            // x为父结点的左子
            if (RBNodeX == parentX.left) {
                // x 的兄弟结点
                brother = parentX.right;
                // 1.（x为“黑+黑”）b为红
                if (isRed(brother)) {
                    // CASE-A1 ：b变黑，p变红，p左旋，重置兄弟b
                    setBlack(brother);
                    setRed(parentX);
                    lRotate(parentX);
                    brother = parentX.right;
                }

                // 2.（x为“黑+黑”）b为黑，bl为黑，br为黑
                // 此时b肯定为黑，b为红时经过旋转，新的b也为黑
                // null 也表示黑色
                if ((brother.left == null || isBlack(brother.left)) &&
                        (brother.left == null || isBlack(brother.right))) {
                    // CASE-A2 ：b变红，p设为新的x（RBNodeX）
                    // 额外黑色上浮（虚拟黑色，想象中的黑色）
                    setRed(brother);
                    RBNodeX = parentX;
                    // 新的parentX
                    parentX = parentOf(RBNodeX);
                } else {
                    if (isRed(brother.left) &&
                            (brother.right == null || isBlack(brother.right))) {
                        // 3.（x为“黑+黑”）b为黑，bl为红，br为黑
                        // CASE-A3 ：b和bl换色，b右旋，重置兄弟b
                        // 换色是为了旋转后保持红黑规则
                        setBlack(brother.left);
                        setRed(brother);
                        rRotate(brother);
                        brother = parentX.right;
                    }
                    // 4.（x为“黑+黑”）b为黑，br为红，bl任意颜色
                    // CASE-A4 ：p的颜色给b，p变黑，br变黑，p左旋，设置x为根结点
                    setColor(brother, parentX.color);
                    setBlack(parentX);
                    setBlack(brother.right);
                    lRotate(parentX);
                    RBNodeX = this.rbtRoot;
                    continue;
                }
            } else {
                // x为父结点的右子，兄弟为左子
                brother = parentX.left;
                // CaseB1 b红
                if (isRed(brother)) {
                    setBlack(brother);
                    setRed(parentX);
                    rRotate(parentX);
                    brother = parentX.left;
                }

                // CaseB2 b黑，bl，br黑
                if ((brother.left == null || isBlack(brother.left)) &&
                        (brother.right == null || isBlack(brother.right))) {
                    // 额外黑色上浮（虚拟黑色，想象中的黑色）
                    setRed(brother);
                    RBNodeX = parentX;
                    // 新的parentX
                    parentX = parentOf(RBNodeX);
                } else {
                    // CaseB3 br红，bl黑，不顺链
                    if (isRed(brother.right) && isBlack(brother.left)) {
                        // 换色是为了旋转后保持红黑规则
                        setRed(brother);
                        setBlack(brother.right);
                        lRotate(brother);
                        brother = parentX.left;
                    }
                    // CaseB4 bl红，顺链
                    // p，b换色旋转，p和bl变黑，为了保持红黑规则，即可消去x额外的虚拟黑色（想象中的黑色） 流过的黑色数一致
                    // 父结点颜色不确定，可能红可能黑
                    setColor(brother, parentX.color);
                    setBlack(parentX);
                    setBlack(brother.left);
                    rRotate(parentX);
                    // 修正完成，退出条件
                    RBNodeX = this.rbtRoot;
                }
            }
        }
        if (RBNodeX != null) {
            setBlack(RBNodeX);
        }
    }

    /************************分割线 测试**************************/
    public static void main(String[] args) {
        RBTree<Integer> rbTree = new RBTree<>();

        rbTree.insert(80);
        rbTree.insert(60);
        rbTree.insert(90);

        rbTree.insert(50);
        rbTree.insert(75);
        rbTree.insert(85);
        rbTree.insert(100);

        rbTree.insert(40);
        rbTree.insert(55);
        rbTree.insert(70);
        rbTree.insert(79);

        System.out.println("先序遍历");
        rbTree.preOrderRecur();
        System.out.println();
        System.out.println("中序遍历");
        rbTree.inOrderRecur();
        System.out.println();
        System.out.println("后序遍历");
        rbTree.postOrderRecur();
        System.out.println();

        rbTree.insert(69);

        System.out.println("******************");
        System.out.println("先序遍历");
        rbTree.preOrderRecur();
        System.out.println();
        System.out.println("中序遍历");
        rbTree.inOrderRecur();
        System.out.println();
        System.out.println("后序遍历");
        rbTree.postOrderRecur();
        System.out.println();
        System.out.println("层序遍历");
        rbTree.levelOrder();
        System.out.println();

        System.out.println("删除79");

        rbTree.remove(79);

        System.out.println("********删除79后**********");
        System.out.println("先序遍历");
        rbTree.preOrderRecur();
        System.out.println();
        System.out.println("中序遍历");
        rbTree.inOrderRecur();
        System.out.println();
        System.out.println("后序遍历");
        rbTree.postOrderRecur();
        System.out.println();
        System.out.println("层序遍历");
        rbTree.levelOrder();
        System.out.println();

        /**----------------------------------------*/
    }
}












